An amusing note from Alan Kay's Re-inventing Programming NSF grant:
A simple example is that it is possible to define sorting in Prolog as a permutation of the inputs that obey a particular pairwise relationship. This is really simple and will work, but Prolog has no recourse but to generate all possible permutations of the input until one is found that satisfies the predicate.
Using this sorting algorithm in Prolog is only one step above Bogo-Sort. (It is one step above Bogo-Sort, as this sort never repeats a permutation, while Bogo-Sort might repeat any permutation depending on the randomization implementation.)
